package com.fufu.algorithem.sort;

import java.util.Arrays;

/**
 * @author: BlcakTiger
 * @date: 2023/2/24 14:11
 * @contact: hsf6661@163.com
 */
public class Shell {

    public static void main(String[] args) {
        //初始化数组
        int[] arr = new int[80000];
        //随机赋值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*1000000);
        }
        //记录执行排序前的时间
        long ori = System.currentTimeMillis();
        //排序
        sortByInsert(arr);
        //记录排序后的时间
        long cur = System.currentTimeMillis();
        //计算时间
        System.out.println((cur-ori)*1.0/1000);
//                int arr[] = {5,4,3,2,1,8,9};
//        sortByInsert(arr);
//        System.out.println(Arrays.toString(arr));
    }

    public static void sortByBubbing(int[] arr){
        //控制增量
        for (int gap = arr.length/2;gap>0;gap/=2) {
            //分组之后直接采用冒泡思路对每一组进行排序
            for (int i = 0;i<arr.length-gap;i+=gap){
                for (int j = 0;j<arr.length-gap-i;j+=gap){
                    if (arr[j] > arr[j + gap]) {
                        arr[j] = arr[j] ^ arr[j + gap];
                        arr[j + gap] = arr[j] ^ arr[j + gap];
                        arr[j] = arr[j] ^ arr[j + gap];
                    }
                }

            }
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void fullEditionShellSort(int arr[]) {
        //控制增量
        for(int gap=arr.length/2;gap>0;gap/=2) {
            // 9 8 7 6 5 4 3 2 1
            for(int i=gap;i<arr.length;i++) {
                int index = i;
                int temp = arr[i];
                //这里利用了插入排序提高效率，减少了不必要的交换
                while(index - gap >=0 && temp < arr[index-gap]) {
                    arr[index] = arr[index-gap];
                    index-=gap;
                }

                arr[index] = temp;
            }
        }
    }

    public static void sortByInsert(int[] arr){
        int insertIndex = 0;
        int val;
        //控制增量
        for (int gap = arr.length/2; gap > 0; gap/=2) {
            //遍历每一组的元素
            for (int j = gap;j<arr.length;j+=gap){
                val = arr[j];

                insertIndex = j-gap;
                //插入排序
                while (insertIndex>=0 && arr[insertIndex]>val){
                    arr[insertIndex+gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                arr[insertIndex+gap] = val;
            }
        }
    }
}
